package hDOJ;

import java.util.Arrays;
import java.util.Scanner;

/*
Problem Description
输入三个字符后，按各字符的ASCII码从小到大的顺序输出这三个字符。
 

Input
输入数据有多组，每组占一行，有三个字符组成，之间无空格。
 

Output
对于每组输入数据，输出一行，字符中间用一个空格分开。
 

Sample Input
qwe
asd
zxc
 

Sample Output
e q w
a d s
c x z



 */

public class Main2000 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        /*
        while (scan.hasNext()) {
            String str = scan.next();
            char[] ch = new char[3];
            for (int i = 0; i < str.length(); i++) {
                ch[i] = str.charAt(i);
            }
            
            // 人工排
            if (ch[0] <= ch[1] && ch[1] <= ch[2]) {
                System.out.println(ch[0] + " " + ch[1] + " " + ch[2]);
            } else if (ch[0] <= ch[2] && ch[2] <= ch[1]) {
                System.out.println(ch[0] + " " + ch[2] + " " + ch[1]);
            } else if (ch[1] <= ch[0] && ch[0] <= ch[2]) {
                System.out.println(ch[1] + " " + ch[0] + " " + ch[2]);
            } else if (ch[1] <= ch[2] && ch[2] <= ch[0]) {
                System.out.println(ch[1] + " " + ch[2] + " " + ch[0]);
            } else if (ch[2] <= ch[1] && ch[1] <= ch[0]) {
                System.out.println(ch[2] + " " + ch[1] + " " + ch[0]);
            } else if (ch[2] <= ch[0] && ch[0] <= ch[1]) {
                System.out.println(ch[2] + " " + ch[0] + " " + ch[1]);
            }
            
            // 冒泡排序
            for (int i = 0; i < ch.length - 1; i++) {
                for (int j = 0; j < ch.length - i - 1; j++) {
                    if (ch[j] > ch[j+1]) {
                        char temp = ch[j];
                        ch[j] = ch[j+1];
                        ch[j+1] = temp;
                    }
                }
            }
            for (int i = 0; i < ch.length - 1; i++) {
                System.out.print(ch[i] + " ");
            }
            System.out.print(ch[ch.length-1]);
            System.out.println();
        }
        */
        int[] arr = {4, 3, 6, 5, 1, 2};
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            //定义基准数，默认为数组的第一个元素
            int temp=arr[left];
            while(left<right) {
                //因为默认的基准数是在最左边，所以首先从右边开始比较进入while循环的判断条件
                //如果当前arr[right]比基准数大，则直接将右指针左移一位，当然还要保证left<right
                while(left<right && arr[right]>temp) {
                    right--;
                }
                //跳出循环说明当前的arr[right]比基准数要小，那么直接将当前数移动到基准数所在的位置，并且左指针向右移一位（left++）
                //这时当前数（arr[right]）所在的位置空出，需要从左边找一个比基准数大的数来填充。
                if(left<right) {
                    arr[left++]=arr[right];
                }
                //下面的步骤是为了在左边找到比基准数大的数填充到right的位置。
                //因为现在需要填充的位置在右边，所以左边的指针移动，如果arr[left]小于或者等于基准数，则直接将左指针右移一位
                while(left<right && arr[left]<=temp) {
                    left++;
                }
                //跳出上一个循环说明当前的arr[left]的值大于基准数，需要将该值填充到右边空出的位置，然后当前位置空出。
                if(left<right) {
                    arr[right--]=arr[left];
                }
                
            }
            //当循环结束说明左指针和右指针已经相遇。并且相遇的位置是一个空出的位置，
            //这时候将基准数填入该位置，并返回该位置的下标，为分区做准备。
            arr[left]=temp;
            System.out.println(Arrays.toString(arr));
        }

    }

}
